class Solution:
    def combinationSum3(self, k: int, n: int) -> list:
        if n > (19 - k) * k / 2 or k > 9:
            return []
        res, i = [], -1
        mid_list = [i for i in range(1, k + 1)]
        try:
            while True:
                if sum(mid_list) == n:
                    res.append(mid_list[:])
                mid_list[-1] += 1
                while mid_list[i] >= 11 + i:
                    mid_list[i-1] += 1
                    i -= 1
                    if i < -k:
                        raise StopIteration
                while i < -1:
                    mid_list[i+1] = mid_list[i] + 1
                    i += 1
        except:
            return res


a = Solution()
print(a.combinationSum3(3, 7))
print(a.combinationSum3(3, 9))
